Article 5316

Title of the article

ON A FINITE BASIS SET FOR SUPERPOSITION IN THE CLASS OF FUNCTIONS COMPUTABLE ON NONDESTRUCTIVE TURING MACHINES WITH OUTPUT

Authors

Osipov Kirill Vladimirovich, Postgraduate student, Lomonosov Moscow State University (1 Leninskie Gory street, Moscow, Russia), d503@acmer.me

Index UDK

519.716

DOI

10.21685/2072-3040-2016-3-5

Abstract

Background. More than 60 years ago A. Grzegorczyk couched the problem of existence of finite basis sets for superposition in classes of recursive functions,which create a hierarchy of the set of all primitive recursive functions. This problem was resolved by various authors for many large and meaningful interesting classes of recursive functions. Resulting from an increased interest to the study of polynomial- time computable functions over the last years, this issue again has been considered for relatively small classes of such functions. In particular, classes of functions that are polynomial-time computable for different variants of Turing machines, which comply with strong restrictions on the structure and methods of operation with external memory, are of great interest right now. The solution of the problem of existence of a finite basis set for superposition in such classes of functions would allow us to understand the nature of polynomial computation deeper and may adduce additional arguments to the solution of the problem of a ratio of deterministic and nonedeterministic polynomial calculations. The aim of this work is to build a finite basis set for superposition in the C-class of functions, (polynomial-time) computable at nondestructive Turing machines with output. The C-class has been recently introduced by S. S. Marchenkov for obtaining the "upper boundary" of the complexity of computing functions, obtained by a limited prefix of the concatenation, and has not been explicitly studied.
Materials and methods. There was employed the method of proving the existence of a finite basis for superposition, based on the use of a quasi-universal function.
Results and conclusions. The author built quasi-universal functions for the C-class of functions computable at nondestructive Turing machines with output. The resulting function is used to obtain a finite basis for superposition in the C-class. This result can be applied to solve similar problems in classes of computable functions that are close to the C-class.

Key words

nondestructive Turing machines with output, polynomial calculations, finite basis set for superposition.

Download PDF
References

1. Grzegorczyk A. Rozprawy Matematyczne [Mathematical apparatus]. 1953, vol. 4, pp. 1–46.
2. Rödding D. Z. Math. Logik Grundlagen Math. [Foundations of mathematical logic].1964,vol.10,pp.315–330.
3. Marchenkov S. S. Matematicheskie zametki [Mathematical notes]. 1969, vol. 5, no. 5, pp. 561–568.
4. Volkov S. A. Diskretnaya matematika [Discrete mathematics]. 2006, vol. 18, no. 4, pp. 31–44.
5. Mazzanti S. Mathematical Logic Quarterly. 2002, vol. 48, pp. 93–104.
6. Marchenkov S. S. Matematicheskie voprosy kibernetiki [Mathematical problems of cybernetics]. 1991, iss. 3, pp. 115–139.
7. Osipov K. V. Vestnik Moskovskogo universiteta. Ser. 15. Vychislitel'naya matematika i kibernetika [Bulletin of Moscow University. Series 15. Calculus mathematics and cybernetics]. 2016, no. 1, pp. 28–34.
8. Marchenkov S. S. Diskretnaya matematika [Discrete mathematics]. 2015, vol. 27, no. 3, pp. 44–55.

 

Дата создания: 19.12.2016 11:17
Дата обновления: 19.12.2016 16:19